Transforms may be employed to convert data from one domain to another domain. A discrete cosine transform (DCT) may be used to transform data from a spatial domain to a frequency domain and an inverse discrete cosine transform (IDCT) may be used to transform data from the frequency domain to the spatial domain. DCT may be used for image/video compression to spatially decorrelate blocks of picture elements (pixels) in images or video frames. The resulting transform coefficients may be much less dependent on each other, which makes these coefficients particularly suitable for quantization and encoding. DCT also exhibits energy compaction property, i.e., the ability to map most of the energy of a block of pixels to only few (typically low order) transform coefficients, which can simplify the design of encoding algorithms and/or ameliorate the amount of data being transmitted
The DCT is widely regarded as the best suboptimal orthogonal transform for the purposes of energy compaction, especially with regard to natural images. That is, its ability to concentrate the energy of natural images into a relatively small number of transform coefficients closely approximates the optimal Karhunen-Loeve transform (KLT). The DCT is also a unitary transform which means that it is comprised of orthonormal basis functions (the norm of each of its basis vectors is one) and its inverse is its transpose. Type-2 DCT is the most widely deployed in popular still image and video standards such as JPEG7, MPEG18, MPEG 29, H.26310, and MPEG 411 and also serves as the definition for the fixed-point implementation that approximates it in MPEG C (ISO/IEC 23002-2), the disclosures of which are hereby incorporated by reference in their entireties herein.
A two-dimensional Type-2 DCT of an M-by-N matrix f is defined below in equation (1) as:
            F      ⁡              (                  u          ,          v                )              =                  c        ⁡                  (          u          )                    ⁢              c        ⁡                  (          v          )                    ⁢                        ∑                      x            =            0                                M            -            1                          ⁢                              ∑                          y              =              0                                      N              -              1                                ⁢                                    f              ⁡                              (                                  x                  ,                  y                                )                                      ⁢            cos            ⁢                                                            (                                                            2                      ⁢                      x                                        +                    1                                    )                                ⁢                u                ⁢                                                                  ⁢                π                                            2                ⁢                M                                      ⁢            cos            ⁢                                                            (                                                            2                      ⁢                      y                                        +                    1                                    )                                ⁢                v                ⁢                                                                  ⁢                π                                            2                ⁢                N                                                          ,          ⁢      0    ≤    x    ≤          M      -      1        ,      0    ≤    y    ≤          N      -      1      
wherein:
      c    ⁡          (      v      )        =      {                                                                      1                                  N                                            ,                                                          v              =              0                                                                                          2                                                      2                    /                    N                                                              ,                                                          1              ≤              v              ≤                              N                -                1                                                        ;                          ⁢                        c          ⁡                      (            u            )                          =                  {                                                                                                                1                                              M                                                              ,                                                                                        u                    =                    0                                                                                                                                          2                                                                        2                          /                          M                                                                                      ,                                                                                        1                    ≤                    u                    ≤                                          M                      -                      1                                                                                            ;                              and
f(x, y) represents a two-dimensional input matrix of sample values and F(u, v) represents a two-dimensional coefficient matrix as an M-by-N matrix of transform coefficients.
The matrix f(x, y) can be perfectly reconstructed from F(u, v) by application of the corresponding IDCT as defined below in equation (2):
            f      ⁡              (                  x          ,          y                )              =                  ∑                  u          =          0                          M          -          1                    ⁢                        ∑                      v            =            0                                N            -            1                          ⁢                              c            ⁡                          (              u              )                                ⁢                      c            ⁡                          (              v              )                                ⁢                      F            ⁡                          (                              u                ,                v                            )                                ⁢          cos          ⁢                                                    (                                                      2                    ⁢                    x                                    +                  1                                )                            ⁢              u              ⁢                                                          ⁢              π                                      2              ⁢              M                                ⁢          cos          ⁢                                                    (                                                      2                    ⁢                    y                                    +                  1                                )                            ⁢              v              ⁢                                                          ⁢              π                                      2              ⁢              N                                            ,          ⁢      0    ≤    x    ≤          M      -      1        ,      0    ≤    y    ≤          N      -      1      
The DCT is a separable transform as defined below in equation (3):
      F    ⁡          (              u        ,        v            )        =            c      ⁡              (        u        )              ⁢                  ∑                  x          =          0                          M          -          1                    ⁢                        f          ⁡                      (                          x              ,              y                        )                          ⁢        cos        ⁢                                            (                                                2                  ⁢                  x                                +                1                            )                        ⁢            u            ⁢                                                  ⁢            π                                2            ⁢            M                          ⁢                  c          ⁡                      (            v            )                          ⁢                              ∑                          y              =              0                                      N              -              1                                ⁢                      f            ⁢                          (                              x                ,                y                            )                        ⁢            cos            ⁢                                                            (                                                            2                      ⁢                      y                                        +                    1                                    )                                ⁢                v                ⁢                                                                  ⁢                π                                            2                ⁢                N                                                        
The corresponding basis functions may be as follows:
sf=0.353553
p=0,m=0,coeff=1.0000000000000000
p=0,m=1,coeff=1.0000000000000000
p=0,m=2,coeff=1.0000000000000000
p=0,m=3,coeff=1.0000000000000000
p=0,m=4,coeff=1.0000000000000000
p=0,m=5,coeff=1.0000000000000000
p=0,m=6,coeff=1.0000000000000000
p=0,m=7,coeff=1.0000000000000000
sf=0.500000
p=1,m=0,coeff=0.9807852804032304
p=1,m=1,coeff=0.8314696123025452
p=1,m=2,coeff=0.5555702330196023
p=1,m=3,coeff=0.1950903220161283
p=1,m=4,coeff=−0.1950903220161282
p=1,m=5,coeff=−0.5555702330196020
p=1,m=6,coeff=−0.8314696123025453
p=1,m=7,coeff=−0.9807852804032304
sf=0.500000
p=2,m=0,coeff=0.9238795325112867
p=2,m=1,coeff=0.3826834323650898
p=2,m=2,coeff=−0.3826834323650897
p=2,m=3,coeff=−0.9238795325112867
p=2,m=4,coeff=−0.9238795325112867
p=2,m=5,coeff=−0.3826834323650903
p=2,m=6,coeff=0.3826834323650900
p=2,m=7,coeff=0.9238795325112865
sf=0.500000
p=3,m=0,coeff=0.8314696123025452
p=3,m=1,coeff=−0.1950903220161282
p=3,m=2,coeff=−0.9807852804032304
p=3,m=3,coeff=−0.5555702330196022
p=3,m=4,coeff=0.5555702330196018
p=3,m=5,coeff=0.9807852804032304
p=3,m=6,coeff=0.1950903220161288
p=3,m=7,coeff=−0.8314696123025451
sf=0.500000
p=4,m=0,coeff=0.7071067811865476
p=4,m=1,coeff=−0.7071067811865475
p=4,m=2,coeff=−0.7071067811865477
p=4,m=3,coeff=0.7071067811865475
p=4,m=4,coeff=0.7071067811865477
p=4,m=5,coeff=−0.7071067811865467
p=4,m=6,coeff=−0.7071067811865472
p=4,m=7,coeff=0.7071067811865466
sf=0.500000
p=5,m=0,coeff=0.5555702330196023
p=5,m=1,coeff=−0.9807852804032304
p=5,m=2,coeff=0.1950903220161283
p=5,m=3,coeff=0.8314696123025456
p=5,m=4,coeff=−0.8314696123025451
p=5,m=5,coeff=−0.1950903220161280
p=5,m=6,coeff=0.9807852804032307
p=5,m=7,coeff=−0.5555702330196015
sf=0.500000
p=6,m=0,coeff=0.3826834323650898
p=6,m=1,coeff=−0.9238795325112867
p=6,m=2,coeff=0.9238795325112865
p=6,m=3,coeff=−0.3826834323650898
p=6,m=4,coeff=−0.3826834323650906
p=6,m=5,coeff=0.9238795325112867
p=6,m=6,coeff=−0.9238795325112863
p=6,m=7,coeff=0.3826834323650896
sf=0.500000
p=7,m=0,coeff=0.1950903220161283
p=7,m=1,coeff=−0.5555702330196022
p=7,m=2,coeff=0.8314696123025456
p=7,m=3,coeff=−0.9807852804032307
p=7, m=4, coeff=0.9807852804032304
p=7,m=5,coeff=−0.8314696123025450
p=7,m=6,coeff=0.5555702330196015
p=7,m=7,coeff=−0.1950903220161286
(sf is the scale factor used to scale the resulting coefficients.)
As noted, the DCT is an analysis tool suitable for separating an image or video signal into its frequency components so that the magnitudes of those frequency components can be subsequently tuned to achieve a desired level of compression for the original image or video signal. The DCT is typically performed using a set of cosine basis functions that are selected to be orthonormal, i.e., the corresponding basis functions are then used to analyze both the vertical and horizontal frequencies of the input signal when images or video using the same basis functions.
The DCT in common image and video systems, such as but not necessarily limited to that described ISO/IEC 23008-2 High Efficiency Video Coding (HEVC), the disclosure of which is hereby incorporated by reference in its entirety herein, is designed due to the common treatment of vertical and horizontal frequencies to operate on square blocks of sample values, e.g., blocks that are either 4×4, 8×8, 16×16, or 32×32 samples in size. Application of such square transform functions can be problematic if the underlying data, signal, image, video, etc. is not square or otherwise fails to share the characteristics that cause square samples to be beneficially transformed using the DCT noted above.